#include "SDL.h"
#include <string>
using namespace std;

#ifdef _WIN32
#include "SDL_image.h"
#include "SDL_ttf.h"
//#define RELEASE
#ifdef RELEASE
const string resourcePath = ".\\resources\\";
#else
const string resourcePath = "C:\\Documents and Settings\\ryan\\My Documents\\C++ Projects\\Enigma Physics Engine SVN\\Test code\\resources\\";
#endif
#else
#include "SDL_image/SDL_image.h"
#include "SDL_ttf/SDL_ttf.h"
const string resourcePath = "Enigma.app/Contents/Resources/";
//const string resourcePath = "/Users/Darryl/Desktop/Programming/Enigma Physics Engine/Test code/resources/";
#endif

#include "SDL_graphics.h"
#include <stdlib.h>
#include <stdio.h>
#include "Enigma.h"
#include <time.h>
#include <list>

const string fontName = "Trebuchet MS.ttf";

enum mode {SAND, LINES, LINESTAR, STARMODE};

const int SCREEN_WIDTH = 1024;
const int SCREEN_HEIGHT = 768;
const int SCREEN_DEPTH = 32;
const int HALF_WIDTH = SCREEN_WIDTH >> 1;
const int HALF_HEIGHT = SCREEN_HEIGHT >> 1;


//num sand cannot be <= num lines!
const int NUM_SAND = 50000;
const int NUM_LINES = 100;
const int NUM_SMALL_STARS = 4000;
const int NUM_MED_STARS = 100;
const int NUM_LARGE_STARS = 5;
const int NUM_STARS = NUM_SMALL_STARS + NUM_MED_STARS + NUM_LARGE_STARS;
const int TICKS_PER_SEC = 1000;
const int LARGEST_OBJECT_WIDTH = 64;

const float PI = 3.141592653;
const float SPRING_CONSTANT = 0.01;
const float MAG_INC = 1.5;
const float MAG_DEC = 0.75;
const float RAD_INC = 1.1;
const float RAD_DEC = 0.9;
const float STAR_RADIUS1 = 2.0; // 4x4 pixels
const float STAR_RADIUS2 = 8.0; // 16x16 pixels
const float STAR_RADIUS3 = 32.0; // 64x64 pixels
const float STAR_MASS1 = 1.0;
const float STAR_MASS2 = 16.0;
const float STAR_MASS3 = 256.0;

SDL_Color fontColor = {0,255,255};

SDL_Surface* screen, *star1, *star2, *star3, *overlay, *momentumDisplay, *energyDisplay, *frameRateDisplay;

TTF_Font* font;

SDL_Event event;
bool gameOn = true;

typedef struct star
{
	Entity* entity;
	float radius;
	float diamSqrd;
} Star;

Star* stars[NUM_STARS];
Entity* specs[NUM_SAND];
Singularity* singularity;
Singularity blackhole(-400.0, 250.0, 10.0);//magnitude, radius, gravitational constant
RadialAccelerator sucker(0.5, 250.0);
SpringRoot* springs[NUM_SAND];
SpringAxis* spaxis;
Uint32 sandColors[NUM_SAND];
Uint32 starColors[NUM_SMALL_STARS];
list<Star*> *spacePartitions;

void initStars();
void collisionDetect(int numberObjects, int squaresWide, int squaresHigh, float widthFactor, float heightFactor);
void collisionDetect2();
void checkPartition(int i);
void comparePartitions(int i, int j);

int main(int argc, char* argv[])
{
	register int i;
	register int j;
	int clockTicks, currentTicks;
	int num = NUM_SAND;
	int currentMode = SAND;
	int framesCount = 0;
	int sandColorMode = 0;
	int starColorMode = 0;
	int squaresWide; //how wide the screen is in terms of partition squares
	int squaresHigh;
	float widthFactor; //used to convert entity coordinates to space partition coordinates
	float heightFactor;
	float frictionConstant = 0.98;
	Uint32 WHITE, BLACK, RED, GREEN, BLUE, ORANGE;
	bool mouseIsDown = false;
	bool frictionOn = false;
	bool wallsOn = false;
	bool pathsOff = true;
	bool overlayOn = false;
	bool freezeParticlesX = true;
	bool freezeParticlesY = true;
	bool collisionsOn = false;
	bool displayEnergy = false;
	bool displayFrameRateOn = false;
	bool springsOn = false;
	bool springAxesOn = false;
	char buffer[255];
	
	SDL_Init(SDL_INIT_EVERYTHING);
	screen = SDL_SetVideoMode(SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_DEPTH, SDL_SWSURFACE);
	SDL_WM_SetCaption("Enigma Physics Engine Test", NULL);
	SDL_FillRect(screen, &screen->clip_rect, SDL_MapRGB(screen->format,0,0,0));
	
	WHITE = SDL_MapRGB(screen->format, 255,255,255);
	BLACK = SDL_MapRGB(screen->format, 0,0,0);
	RED = SDL_MapRGB(screen->format, 255, 0, 0);
	GREEN = SDL_MapRGB(screen->format, 0, 255, 0);
	BLUE = SDL_MapRGB(screen->format, 0, 0, 255);
	ORANGE = SDL_MapRGB(screen->format, 255, 175, 0);
	
	TTF_Init();
	font = TTF_OpenFont((resourcePath + fontName).c_str(), 24);
	overlay = renderBlockText("Colors Toggle [TAB]\nCollisions Toggle [C]\nDecrease Radius [D]\nMomentum and Kinetic Energy Display [E]\nFriction Toggle [F]\nGlobal Force Toggle [G]\nIncrease Radius [I]\nSpringAxes Toggle [J]\nSpringRoot Toggle [K]\nLess Force [L]\nMore Force [M]\nOverlay Menu [O]\nParticle Paths On [P]\nDisplay Frame Rate [Q]\nReset Particles [R]\nSwitch Singularity/Accelerator [S]\nToggle Force Direction [T]\nWalls On [W]\nFreeze X Velocity on Mouse Up [X]\nFreeze Y Velocity on Mouse Up [Y]\nExit [ESC]\nRotate Spring Axis [Arrow left/right]\nAdjust Friction[Arrow up/down]", font, fontColor, 0, 0, SCREEN_DEPTH);
	energyDisplay = TTF_RenderText_Solid(font, "0", fontColor);
	momentumDisplay = TTF_RenderText_Solid(font, "0", fontColor);
	frameRateDisplay = TTF_RenderText_Solid(font, "0", fontColor);
	
	singularity = &blackhole;
	star1 = sdlLoadImage(resourcePath + "star.png");
	star2 = sdlLoadImage(resourcePath + "star2.png");
	star3 = sdlLoadImage(resourcePath + "star3.png");
	
	srand(time(0));
	initStars();
	
	for (i = 0; i < NUM_SAND; i++) {
		specs[i] = new Entity(Vec2d((float)(rand() % SCREEN_WIDTH), (float)(rand() % SCREEN_HEIGHT)));
		sandColors[i] = WHITE;
		springs[i] = new SpringRoot(SPRING_CONSTANT, 0.0);
		springs[i]->pos = specs[i]->pos;
	}
	for (i = 0; i < NUM_SMALL_STARS; i++)
		starColors[i] = WHITE;
	
	spaxis = new SpringAxis(Vec2d(SCREEN_WIDTH * 0.5, SCREEN_HEIGHT * 0.5), 0.0, 0.001, 0.0);
	
	clockTicks = SDL_GetTicks();
	
	//set up space partitions for collision detection
	squaresWide = SCREEN_WIDTH / LARGEST_OBJECT_WIDTH + 1;
	squaresHigh = SCREEN_HEIGHT / LARGEST_OBJECT_WIDTH + 1;
	spacePartitions = new list<Star*>[squaresHigh * squaresWide];
	widthFactor = squaresWide / (float)SCREEN_WIDTH;
	heightFactor = squaresHigh / (float)SCREEN_HEIGHT;
	
	while (gameOn)
	{
		//----------------------------------- EVENT HANDLING ------------------------------------
		while (SDL_PollEvent(&event))
		{
			switch(event.type)
			{
				case SDL_MOUSEMOTION:
					if (mouseIsDown)
					{
						singularity->pos.x = event.motion.x;
						singularity->pos.y = event.motion.y;
					}
					break;
				case SDL_MOUSEBUTTONDOWN:
					mouseIsDown = true;
					singularity->pos.x = event.motion.x;
					singularity->pos.y = event.motion.y;
					singularity->active = true;
					break;
				case SDL_MOUSEBUTTONUP:
					mouseIsDown = false;
					if (currentMode != STARMODE)
					{
						if (freezeParticlesX)
						{
							for (i = 0; i < num; i++)
								specs[i]->vel.x = 0.0;
						}					
						if (freezeParticlesY)
						{
							for (i = 0; i < num; i++)
								specs[i]->vel.y = 0.0;
						}
					}
					else
					{
						if (freezeParticlesX)
						{
							for (i = 0; i < num; i++)
								stars[i]->entity->vel.x = 0.0;
						}					
						if (freezeParticlesY)
						{
							for (i = 0; i < num; i++)
								stars[i]->entity->vel.y = 0.0;
						}
					}
					singularity->active = false;
					break;
				case SDL_KEYDOWN:
					switch (event.key.keysym.sym)
				    {				
						case SDLK_TAB:							
							if (currentMode == SAND)
							{
								sandColorMode++;
								if (sandColorMode > 2)
									sandColorMode = 0;
								switch (sandColorMode)
								{
									case 0:
										for (int z = 0; z < NUM_SAND; z++)
											sandColors[z] = WHITE;
										break;
									case 1:
										for (int z = 0; z < NUM_SAND; z++)
										{
											if (specs[z]->pos.x > HALF_WIDTH)
												sandColors[z] = WHITE;
											else
												sandColors[z] = RED;
										}
										break;
									case 2:
										for (int z = 0; z < NUM_SAND; z++)
										{
											if (specs[z]->pos.x > HALF_WIDTH)
											{
												if (specs[z]->pos.y > HALF_HEIGHT)
													sandColors[z] = GREEN;
												else
													sandColors[z] = BLUE;
											}
											else
											{
												if (specs[z]->pos.y > HALF_HEIGHT)
													sandColors[z] = ORANGE;
												else
													sandColors[z] = RED;
											}
										}
										break;
								}
							}
							else if (currentMode == STARMODE)
							{
								starColorMode++;
								if (starColorMode > 2)
									starColorMode = 0;
								switch(starColorMode)
								{
									case 0:
										for (int z = 0; z < NUM_SMALL_STARS; z++)
											starColors[z] = WHITE;
										break;
									case 1:
										for (int z = 0; z < NUM_SMALL_STARS; z++)
										{
											if (stars[z]->entity->pos.x > HALF_WIDTH)
												starColors[z] = WHITE;
											else
												starColors[z] = RED;													
										}
										break;
									case 2:
										for (int z = 0; z < NUM_SMALL_STARS; z++)
										{
											if (stars[z]->entity->pos.x > HALF_WIDTH)
											{
												if (stars[z]->entity->pos.y > HALF_HEIGHT)
													starColors[z] = GREEN;
												else
													starColors[z] = BLUE;
											}
											else
											{
												if (stars[z]->entity->pos.y > HALF_HEIGHT)
													starColors[z] = ORANGE;
												else
													starColors[z] = RED;
											}
										}
										break;										
								}
							}
							break;
						case SDLK_UP:
							frictionConstant *= 0.98;
							break;
						case SDLK_DOWN:							
							frictionConstant *= 1.02;
							if (frictionConstant > 1.0)
								frictionConstant = 1.0;
							break;
						case SDLK_c:
							collisionsOn = !collisionsOn;
							break;
						case SDLK_d:
							singularity->setEffectiveRadius(singularity->getEffectiveRadius() * RAD_DEC);
							break;			
						case SDLK_e:
							displayEnergy = !displayEnergy;
							break;
						case SDLK_f:
							frictionOn = !frictionOn;
							break;						
						case SDLK_g:
							singularity->global = !singularity->global;
							break;
						case SDLK_i:
							singularity->setEffectiveRadius(singularity->getEffectiveRadius() * RAD_INC);
							break;
						case SDLK_j:
							springAxesOn = !springAxesOn;
							break;
						case SDLK_k:
							springsOn = !springsOn;
							break;
						case SDLK_l:
							blackhole.magnitude *= MAG_DEC;
						    sucker.effectiveAcceleration *= MAG_DEC;
							break;
						case SDLK_m:
							blackhole.magnitude *= MAG_INC;
						    sucker.effectiveAcceleration *= MAG_INC;
							break;																														
						case SDLK_o:
							overlayOn = !overlayOn;
							break;
						case SDLK_p:
							pathsOff = !pathsOff;
							break;
						case SDLK_q:
							displayFrameRateOn = !displayFrameRateOn;
							break;
						case SDLK_r:
							currentMode++;
							if (currentMode > 3)
								currentMode = 0;							
							switch(currentMode)
						    {
								case SAND:
									for (i = 0; i < NUM_SAND; i++)
									{
										specs[i]->pos.x = (float)(rand() % SCREEN_WIDTH);
										specs[i]->pos.y = (float)(rand() % SCREEN_HEIGHT);
										springs[i]->pos = specs[i]->pos;
									}
									break;
								case LINES:									
								case LINESTAR:
									for (i = 0; i < NUM_LINES; i++)
									{
										specs[i]->pos.x = (float)(rand() % SCREEN_WIDTH);
										specs[i]->pos.y = (float)(rand() % SCREEN_HEIGHT);
										springs[i]->pos = specs[i]->pos;
									}
									//springForce test:
									specs[0]->pos.x = 100.0;
									specs[0]->pos.y = 100.0;
									specs[NUM_LINES >> 1]->pos.x = 200.0;
									specs[NUM_LINES >> 1]->pos.y = 100.0;
									//end test
									break;
								case STARMODE:
									for (i = 0; i < NUM_STARS; i++)
									{
										stars[i]->entity->pos.x = (float)(rand() % SCREEN_WIDTH);
										stars[i]->entity->pos.y = (float)(rand() % SCREEN_HEIGHT);
									}
									break;							
						    }							 
							break;
						case SDLK_z:
							//springForce test:
							specs[0]->vel.x = 3.0;
							//end test
							break;
						case SDLK_s:
							if (singularity == &blackhole)
								singularity = (Singularity*)&sucker;
							else
								singularity = &blackhole;
							break;
						case SDLK_t:
							blackhole.magnitude = -blackhole.magnitude;
						    sucker.effectiveAcceleration = -sucker.effectiveAcceleration;
							break;
						case SDLK_w:
							wallsOn = !wallsOn;
							break;
						case SDLK_x:
							freezeParticlesX = !freezeParticlesX;
							break;
						case SDLK_y:
							freezeParticlesY = !freezeParticlesY;
							break;
						case SDLK_ESCAPE:
							gameOn = false;
							break;
				    }
					break;
				case SDL_QUIT:
					gameOn = false;
					break;
			}
		} // end while(poll events)
		
		Uint8* keystates = SDL_GetKeyState(NULL);
		if (keystates[SDLK_LEFT])
			spaxis->setDirection(spaxis->getDirection() + 0.025);
		if (keystates[SDLK_RIGHT])
			spaxis->setDirection(spaxis->getDirection() - 0.025);
		
		//-------------------------------------- SIMULATION LOGIC ---------------------------------------------
		
		switch (currentMode)
		{
			case SAND:
				num = NUM_SAND;
				break;
			case LINES:
			case LINESTAR:
				num = NUM_LINES;
				break;
			case STARMODE:	
				num = NUM_STARS;
				break;
		}
		
		if (currentMode == STARMODE)
		{
			if (collisionsOn)
				collisionDetect(num, squaresWide, squaresHigh, widthFactor, heightFactor);
				//collisionDetect2();
			
			for (i = 0; i < num; i++)
			{
				if (singularity->active)
					singularity->affect(stars[i]->entity);
				if (wallsOn)
				{
					if ((stars[i]->entity->pos.x - stars[i]->radius < 0 && stars[i]->entity->vel.x < 0) || (stars[i]->entity->pos.x + stars[i]->radius > SCREEN_WIDTH && stars[i]->entity->vel.x > 0))
						stars[i]->entity->vel.x = -stars[i]->entity->vel.x;
					if ((stars[i]->entity->pos.y - stars[i]->radius < 0 && stars[i]->entity->vel.y < 0) || (stars[i]->entity->pos.y + stars[i]->radius > SCREEN_HEIGHT && stars[i]->entity->vel.y > 0))
						stars[i]->entity->vel.y = -stars[i]->entity->vel.y;
				}
				if (frictionOn)
				{
					stars[i]->entity->vel.x *= frictionConstant;
					stars[i]->entity->vel.y *= frictionConstant;
				}
				
				stars[i]->entity->update();
				stars[i]->entity->accel.x = 0.0;
				stars[i]->entity->accel.y = 0.0;		
			}
		}
		else //mode is not starmode
		{
			if (currentMode == LINESTAR)
				springForce(*specs[0], *specs[NUM_LINES >> 1], 0.01, 100.0);
			
			for (i = 0; i < num; i++)
			{
				if (singularity->active)
					singularity->affect(specs[i]);
				if (springsOn)
					springs[i]->affect(specs[i]);
				if (springAxesOn)
					spaxis->affect(specs[i]);
				if (wallsOn)
				{
					if ((specs[i]->pos.x < 0 && specs[i]->vel.x < 0) || (specs[i]->pos.x > SCREEN_WIDTH && specs[i]->vel.x > 0))
						specs[i]->vel.x = -specs[i]->vel.x;
					if ((specs[i]->pos.y < 0 && specs[i]->vel.y < 0) || (specs[i]->pos.y > SCREEN_HEIGHT && specs[i]->vel.y > 0))
						specs[i]->vel.y = -specs[i]->vel.y;
				}
				if (frictionOn)
				{
					specs[i]->vel.x *= frictionConstant;
					specs[i]->vel.y *= frictionConstant;
				}
									
				specs[i]->update();
				specs[i]->accel.x = 0.0;
				specs[i]->accel.y = 0.0;				
			}
		}
		
		//----------------------------------- GRAPHICS ---------------------------------------
		
		if (pathsOff)
			SDL_FillRect(screen, &screen->clip_rect, BLACK); 
		if( SDL_MUSTLOCK(screen))
			SDL_LockSurface(screen);		
		switch (currentMode)
		{
			case SAND:				
				for (i = 0; i < num; i++)
					putpixel32(screen, specs[i]->pos.x, specs[i]->pos.y, sandColors[i]);
				if (springAxesOn)
					line32(screen, SCREEN_WIDTH * 0.5 - 40.0 * cos(spaxis->getDirection()),
						           SCREEN_HEIGHT * 0.5 + 40.0 * sin(spaxis->getDirection()),
						           SCREEN_WIDTH * 0.5 + 40.0 * cos(spaxis->getDirection()),
						           SCREEN_HEIGHT * 0.5 - 40.0 * sin(spaxis->getDirection()), WHITE);
				break; 
			case LINES:				
				for (i = 0; i < num; i++)				
					line32(screen, specs[i]->pos.x, specs[i]->pos.y, specs[i+1]->pos.x, specs[i+1]->pos.y, WHITE);
				break;
			case LINESTAR:
				num = NUM_LINES >> 1;
				for (i = 1; i < num; i++)
					line32(screen, specs[0]->pos.x, specs[0]->pos.y, specs[i]->pos.x, specs[i]->pos.y, WHITE);
				for (i = num + 1; i < NUM_LINES; i++)
					line32(screen, specs[num]->pos.x, specs[num]->pos.y, specs[i]->pos.x, specs[i]->pos.y, WHITE);
				num = NUM_LINES;
				break;
		}
		if( SDL_MUSTLOCK(screen))
			SDL_UnlockSurface(screen);
		
		if (currentMode == STARMODE)
		{
			if (displayEnergy)
			{
				register float energy = 0.f;
				for (i = 0; i < NUM_SMALL_STARS; i++)
				{
					putcircle(screen, stars[i]->entity->pos.x, stars[i]->entity->pos.y, starColors[i]);
					//sdlBlit(stars[i]->entity->pos.x - stars[i]->radius, stars[i]->entity->pos.y - stars[i]->radius, star1, screen, NULL);					
					energy += (stars[i]->entity->vel * stars[i]->entity->vel) * stars[i]->entity->getMass();
				}
				j = NUM_SMALL_STARS + NUM_MED_STARS;
				for (i = NUM_SMALL_STARS; i < j; i++)
				{
					sdlBlit(stars[i]->entity->pos.x - stars[i]->radius, stars[i]->entity->pos.y - stars[i]->radius, star2, screen, NULL);
					energy += (stars[i]->entity->vel * stars[i]->entity->vel) * stars[i]->entity->getMass();
				}				
				for (i = j; i < NUM_STARS; i++)
				{
					sdlBlit(stars[i]->entity->pos.x - stars[i]->radius, stars[i]->entity->pos.y - stars[i]->radius, star3, screen, NULL);
					energy += (stars[i]->entity->vel * stars[i]->entity->vel) * stars[i]->entity->getMass();
				}
				energy *= 0.5f;
				sprintf(buffer, "%3.3f", energy);
				SDL_FreeSurface(energyDisplay);
				energyDisplay = TTF_RenderText_Solid(font, buffer, fontColor);
				TTF_SizeText(font, buffer, &i, NULL);
				sdlBlit(SCREEN_WIDTH - i, 0, energyDisplay, screen, NULL);
			}
			else
			{
				for (i = 0; i < NUM_SMALL_STARS; i++)
					putcircle(screen, stars[i]->entity->pos.x, stars[i]->entity->pos.y, starColors[i]);
					//sdlBlit(stars[i]->entity->pos.x - stars[i]->radius, stars[i]->entity->pos.y - stars[i]->radius, star1, screen, NULL);
				j = NUM_SMALL_STARS + NUM_MED_STARS;
				for (i = NUM_SMALL_STARS; i < j; i++)
					sdlBlit(stars[i]->entity->pos.x - stars[i]->radius, stars[i]->entity->pos.y - stars[i]->radius, star2, screen, NULL);
				for (i = j; i < NUM_STARS; i++)
					sdlBlit(stars[i]->entity->pos.x - stars[i]->radius, stars[i]->entity->pos.y - stars[i]->radius, star3, screen, NULL);
			}
		}
		
		if (overlayOn)
			sdlBlit(0, 0, overlay, screen, NULL);
		if (displayFrameRateOn)
			sdlBlit(0, SCREEN_HEIGHT - TTF_FontHeight(font), frameRateDisplay, screen, NULL);
		
		SDL_Flip(screen);
		
		//------ Calculate frame rate -----------
		currentTicks = SDL_GetTicks() - clockTicks;
		if (currentTicks > TICKS_PER_SEC)
		{
			sprintf(buffer, "%3.1f", (float)framesCount * TICKS_PER_SEC / (float)currentTicks);
			SDL_FreeSurface(frameRateDisplay);
			frameRateDisplay = TTF_RenderText_Solid(font, buffer, fontColor);
			clockTicks = SDL_GetTicks();
			framesCount = 0;
		}
		else
			framesCount++;
		
	} //end while(gameOn)
	
	TTF_CloseFont(font);
	TTF_Quit();
	SDL_FreeSurface(star1);
	SDL_FreeSurface(star2);
	SDL_FreeSurface(star3);
	SDL_FreeSurface(overlay);
	SDL_Quit();
	return 0;
}

void collisionDetect(int numberObjects, int squaresWide, int squaresHigh, float widthFactor, float heightFactor)
{
	int i, j, max1, max2, max3, baseLoc, baseLoc2;
	
	for (i = 0; i < numberObjects; i++)
	{
		if (stars[i]->entity->pos.x < SCREEN_WIDTH && stars[i]->entity->pos.x > 0 && stars[i]->entity->pos.y < SCREEN_HEIGHT && stars[i]->entity->pos.y > 0)
			spacePartitions[(int)(stars[i]->entity->pos.y * heightFactor) * squaresWide + (int)(stars[i]->entity->pos.x * widthFactor)].push_back(stars[i]);
	}	
	
	max1 = squaresHigh - 1;
	max2 = squaresWide - 1;
	for (i = 0; i < max1; i++)
	{
		baseLoc = i * squaresWide;
		
		//find collisions involving first partition in this row
		checkPartition(baseLoc);
		comparePartitions(baseLoc, baseLoc + 1);
		comparePartitions(baseLoc, baseLoc + squaresWide);
		comparePartitions(baseLoc, baseLoc + squaresWide + 1);
		spacePartitions[baseLoc].clear();
		
		//find collisions involving the inner partitions (not left or right boundary)
		for (j = 1; j < max2; j++)
		{
			baseLoc2 = baseLoc + j;
			checkPartition(baseLoc2);
			comparePartitions(baseLoc2, baseLoc2 + 1);
			comparePartitions(baseLoc2, baseLoc2 + squaresWide - 1);
			comparePartitions(baseLoc2, baseLoc2 + squaresWide);
			comparePartitions(baseLoc2, baseLoc2 + squaresWide + 1);
			spacePartitions[baseLoc2].clear();
		}
		
		//find collisions involving the last partition in this row
		checkPartition(baseLoc + max2);
		comparePartitions(baseLoc + max2, baseLoc + (squaresWide << 1) - 1);
		comparePartitions(baseLoc + max2, baseLoc + (squaresWide << 1) - 2);
		spacePartitions[baseLoc + max2].clear();
	}
	max3 = squaresHigh * squaresWide - 1;
	for (i = squaresWide * max1; i < max3; i++)
	{
		checkPartition(i);
		comparePartitions(i, i+1);
		spacePartitions[i].clear();
	}
	checkPartition(max3);
	spacePartitions[max3].clear();
}

void checkPartition(int i)
{	
	if (spacePartitions[i].size() > 1)
	{
		float radiiSum;
		float xDisp, yDisp;		
		list<Star*>::iterator I = spacePartitions[i].begin();
		list<Star*>::iterator J;
		while (*I != spacePartitions[i].back())
		{
			J = ++I;
			I--;
			while (J != spacePartitions[i].end())
			{
				radiiSum = (*I)->radius + (*J)->radius;
				xDisp = (*I)->entity->pos.x - (*J)->entity->pos.x;
				yDisp = (*I)->entity->pos.y - (*J)->entity->pos.y;
				if (xDisp * xDisp + yDisp * yDisp < radiiSum * radiiSum)
					collideSpherical(*((*I)->entity), (*I)->radius, *((*J)->entity), (*J)->radius);
				J++;
			}
			I++;	
		}		
	}
}

void comparePartitions(int i, int j)
{
	if (!spacePartitions[i].empty() && !spacePartitions[j].empty())
	{
		float radiiSum;
		float xDisp, yDisp;		
		list<Star*>::iterator I = spacePartitions[i].begin();
		list<Star*>::iterator J;
		while (I != spacePartitions[i].end())
		{
			J = spacePartitions[j].begin();
			while (J != spacePartitions[j].end())
			{
				radiiSum = (*I)->radius + (*J)->radius;
				xDisp = (*I)->entity->pos.x - (*J)->entity->pos.x;
				yDisp = (*I)->entity->pos.y - (*J)->entity->pos.y;
				if (xDisp * xDisp + yDisp * yDisp < radiiSum * radiiSum)
					collideSpherical(*((*I)->entity), (*I)->radius, *((*J)->entity), (*J)->radius);
				J++;
			}
			I++;	
		}		
	}
}

void collisionDetect2()
{
	int i, j, num;
	float xDisp, yDisp, radiiSum;
	num = NUM_STARS - 1;
	
	for (i = 0; i < num; i++)
	{
		for (j = i; j < NUM_STARS; j++)
		{
			radiiSum = stars[i]->radius + stars[j]->radius;
			xDisp = stars[i]->entity->pos.x - stars[j]->entity->pos.x;
			yDisp = stars[i]->entity->pos.y - stars[j]->entity->pos.y;
			if (xDisp * xDisp + yDisp * yDisp < radiiSum * radiiSum)
				collideSpherical(*(stars[i]->entity), stars[i]->radius, *(stars[j]->entity), stars[j]->radius);
		}
	}
}

void initStars()
{
	register int i;
	int j;
	
	for (i = 0; i < NUM_SMALL_STARS; i++)
	{
		stars[i] = new Star;
		stars[i]->radius = STAR_RADIUS1;
		stars[i]->entity = new Entity(Vec2d((float)(rand() % SCREEN_WIDTH), (float)(rand() % SCREEN_HEIGHT)));
		stars[i]->entity->setMass(STAR_MASS1);
	}
	j = NUM_SMALL_STARS + NUM_MED_STARS;
	for (i = NUM_SMALL_STARS; i < j; i++)
	{
		stars[i] = new Star;
		stars[i]->radius = STAR_RADIUS2;
		stars[i]->entity = new Entity(Vec2d((float)(rand() % SCREEN_WIDTH), (float)(rand() % SCREEN_HEIGHT)));
		stars[i]->entity->setMass(STAR_MASS2);
	}
	for (i = j; i < NUM_STARS; i++)
	{
		stars[i] = new Star;
		stars[i]->radius = STAR_RADIUS3;
		stars[i]->entity = new Entity(Vec2d((float)(rand() % SCREEN_WIDTH), (float)(rand() % SCREEN_HEIGHT)));
		stars[i]->entity->setMass(STAR_MASS3);
	}
}






